package features.advance.leetcode.interview.offer.easy;

/**
 *  剑指 Offer 15. 二进制中1的个数
 *
 *  难度：简单
 *
 * 请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
 *
 *
 *
 * 示例 1：
 *
 * 输入：00000000000000000000000000001011
 * 输出：3
 * 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
 * 示例 2：
 *
 * 输入：00000000000000000000000010000000
 * 输出：1
 * 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
 * 示例 3：
 *
 * 输入：11111111111111111111111111111101
 * 输出：31
 * 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
 *
 *
 * 提示：
 *
 * 输入必须是长度为 32 的 二进制串 。
 *
 *
 * 注意：本题与主站 191 题相同：https://leetcode-cn.com/problems/number-of-1-bits/
 *
 * @author LIN
 * @date 2021-05-17
 */
public class Offer15 {
    /**
     * 解题思路：转成字符串格式，逐个遍历，大于1的记录+1
     * 返回总记录数
     *
     * 题解：位运算 &
     * 若n&1 = 0 ，则n二进制最右一位为0；
     * 若n&1 = 1， 则n二进制最右一位为1。
     *
     * 无符号右移操作：（
     * Java中>>和>>>的区别
     * >>：带符号右移。正数右移高位补0，负数右移高位补1。比如：
     * 4 >> 1，结果是2；-4 >> 1，结果是-2。-2 >> 1，结果是-1。
     * >>>：无符号右移。无论是正数还是负数，高位通通补0。
     * 对于正数而言，>>和>>>没区别。
     * 对于负数而言，-2 >>> 1，结果是2147483647（Integer.MAX_VALUE），-1 >>> 1，结果是2147483647（Integer.MAX_VALUE）。
     * 所以，要判断两个数符号是否相同时，可以这么干：
     * return ((a >> 31) ^ (b >> 31)) == 0;
     * ）
     *
     * 算法流程：
     * 1、初始化数量统计变量res=0。
     * 2、循环逐位判断：当n=0时跳出。
     * 3、返回统计数量res。
     *
     * @param n
     * @return
     */
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        String s = Integer.toBinaryString(n);
        // System.out.println(s);
        int r = 0;
        for(int i=0;i<s.length();i++){
            char a = s.charAt(i);
            if(a == '1'){
                r++;
            }
        }
        return r;
    }


    public static void main(String[] args) {

        int n = 11;
        Offer15 offer15 = new Offer15() {
            // 位运算，效率高
            @Override
            public int hammingWeight(int n) {
                int res = 0;
                for(;n>0;){
                    res += n&1;
                    // 无符号右移，高位补0
                    n>>>=1;
                }
                return res;
            }
        };
        int h = offer15.hammingWeight(n);

        System.out.println(h);

    }
}
